package day0330

import . "gocode/algorithm/utils"

// 左 中 右

func inorderTraversal1(root *TreeNode) (res []int) {
	stk := make([]*TreeNode, 0)
	for len(stk) > 0 || root != nil {
		for root != nil {
			stk = append(stk, root)
			root = root.Left
		}
		root = stk[len(stk)-1]
		stk = stk[:len(stk)-1]
		res = append(res, root.Val)
		root = root.Right
	}
	return
}

var ans []int

func inorderTraversal(root *TreeNode) []int {
	ans = make([]int, 0)
	help(root)
	return ans
}

func help(root *TreeNode) {
	if root != nil {
		help(root.Left)
		ans = append(ans, root.Val)
		help(root.Right)
	}
}
